package company.holala.question;

import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

import org.junit.Test;

/**
 * @author jiangwz
 * @create 2019/11/5.
 */
public class Question {

    public class Menu {
        private int id; // 主键，菜单id
        private String name; // 菜单名称
        private int pid; // 菜单父id，根节点pid=0
        private List<Menu> children; // 下级菜单
        // 省略set、get等方法。

        public int getId() {
            return id;
        }

        public Menu setId(int id) {
            this.id = id;
            return this;
        }

        public String getName() {
            return name;
        }

        public Menu setName(String name) {
            this.name = name;
            return this;
        }

        public int getPid() {
            return pid;
        }

        public Menu setPid(int pid) {
            this.pid = pid;
            return this;
        }
    }
    public Menu getMenuTree(List<Menu> menuList) {
        List<Menu> collect = menuList.stream().sorted(Comparator.comparing(Menu::getId)).collect(Collectors.toList());
        if (collect == null)
            return null;

        Menu rootMenu = collect.get(0);

        return rootMenu;
    }

    @Test
    public void test01(){

        MyMap<String, Object> map = new MyMap<>();

        map.put("22",1);
        map.put("33",1);
        map.put("44",2);
        System.out.println(map.get("44"));


//        HashMap<String, Object> map1 = new HashMap<>();
//        map1.put("22",1);
//        map1.put("33",1);

    }

    interface Map<K,V> {
        V get(Object key);
        V put(K key, V value);
    }

    class  MyMap<K,V> implements Map<K,V> {

        Entry<K,V>[] table;
        static final int DEFAULT_SIZE = 16;
        int CAPACITY = DEFAULT_SIZE;

        public MyMap() {
            table = new Entry[DEFAULT_SIZE];
        }
        public MyMap(int capacity) {
//            if (capacity)
            table = new Entry[capacity];
            this.CAPACITY = capacity;
        }


        public V get(Object key) {
            int index = ((CAPACITY - 1) & hash(key));
            Entry<K, V> e = table[index];
            while (e != null) {
                boolean equals = e.getKey().equals(key);
                if (equals)
                    return (V) e.getValue();
                e = e.getNext();
            }
            return null;
        }

        public int hash(Object key) {
            int h;
            return key==null?0:(h=key.hashCode()) ^ (h>>>16);
        }

        @Override
        public V put(K key, V value) {
            if (table.length == CAPACITY) {
                resize();
            }
            int index = ((CAPACITY - 1) & hash(key));
            if (table[index] == null) {
                table[index] = new Entry<>(key,value,null);
            }else {
                Entry p=table[index];
                for (;;) {
                    Entry next = p.getNext();
                    if (next == null) {
                        p.next = new Entry<>(key,value,null);
                        break;
                    }
                    if (key != null && key.hashCode() == next.getKey().hashCode() && key.equals(next.getKey()))
                        break;
                    p = next;
                }
            }
            return null;
        }

        public Entry<K,V>[] resize(){
            int oldCap = CAPACITY;
            int newSize = CAPACITY << 1;
            Entry<K,V>[] oldTable = table;
            Entry<K,V>[] newTable = new Entry[newSize];
            table = newTable;
            for (int i = 0; i < oldTable.length; i++) {
                Entry<K,V> p;
                if ((p = oldTable[i]) != null) {
                    oldTable[i] = null;//置空
                    if (p.next == null) {
                        newTable[hash(p.key) & newSize-1] = p;
                    }else {
                        Entry<K,V> loHead = null,loTail = null;
                        Entry<K,V> hiHead = null,hiTail = null;
                        Entry<K,V> next;
                        do {
                            next = p.next;
                            if ((hash(p.key) & oldCap) == 0) {
                                if (loTail == null) {
                                    loHead = p;
                                }else {
                                    loTail.next = p;
                                }
                                loTail = p;
                            }else {
                                if (hiTail == null){
                                    hiHead = p;
                                }else {
                                    hiTail.next = p;
                                }
                                hiTail = p;
                            }
                        }while ( (p = next) != null);

                        if (loTail != null) {
                            loTail.next = null;
                            newTable[i] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTable[i+oldCap] = hiHead;
                        }
                    }

                }

            }
            return table;
        }

        class Entry<K,V>{
            int hash;//最好加上这个,免得每次都计算hash值
            Object key;
            Object value;
            Entry next;

            public Entry(Object key, Object value, Entry next) {
                this.key = key;
                this.value = value;
                this.next = next;
            }

            public Object getKey() {
                return key;
            }

            public Entry setKey(Object key) {
                this.key = key;
                return this;
            }

            public Object getValue() {
                return value;
            }

            public Entry setValue(Object value) {
                this.value = value;
                return this;
            }

            public Entry getNext() {
                return next;
            }

            public Entry setNext(Entry next) {
                this.next = next;
                return this;
            }
        }
    }
}
